import math
from collections import Counter
from urllib.request import urlopen
import csv
import random

# 加载数据
def load_data(url):
    response = urlopen(url)
    lines = [l.decode('utf-8') for l in response.readlines()]
    cr = csv.reader(lines)
    data = list(cr)
    return data

# 数据标准化
def standardize_data(data):
    standardized_data = []
    for i in range(1, len(data[0])):  # 跳过标签列
        column = [float(row[i]) for row in data]
        mean = sum(column) / len(column)
        std = math.sqrt(sum((x - mean) ** 2 for x in column) / len(column))
        standardized_column = [(float(value) - mean) / std for value in column]
        standardized_data.append(standardized_column)
    return list(map(list, zip(*standardized_data)))

# 计算欧几里得距离
def euclidean_distance(row1, row2):
    distance = 0.0
    for i in range(len(row1)):
        distance += (float(row1[i]) - float(row2[i])) ** 2
    return math.sqrt(distance)

# 找到 K 个最近邻
def get_neighbors(train, test_row, k):
    distances = []
    for train_row in train:
        dist = euclidean_distance(test_row, train_row[1:])
        distances.append((train_row, dist))
    distances.sort(key=lambda x: x[1])
    neighbors = [distances[i][0] for i in range(k)]
    return neighbors

# 预测分类
def predict_classification(train, test_row, k):
    neighbors = get_neighbors(train, test_row, k)
    output_values = [row[0] for row in neighbors]
    prediction = Counter(output_values).most_common(1)[0][0]
    return prediction

# 主函数
if __name__ == "__main__":
    # 加载数据
    url = "https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data"
    data = load_data(url)

    # 准备数据
    labels = [int(row[0]) for row in data]
    features = [[float(value) for value in row[1:]] for row in data]

    # 数据标准化
    standardized_features = standardize_data(data)

    # 打乱数据
    combined = list(zip(standardized_features, labels))
    random.shuffle(combined)
    standardized_features[:], labels[:] = zip(*combined)

    # 划分训练集和测试集
    train_size = int(0.7 * len(data))
    X_train, X_test = standardized_features[:train_size], standardized_features[train_size:]
    y_train, y_test = labels[:train_size], labels[train_size:]

    # 将训练集和测试集合并为完整的数据集
    train_data = [[y_train[i]] + X_train[i] for i in range(len(y_train))]
    test_data = [[y_test[i]] + X_test[i] for i in range(len(y_test))]

    # 设置 K 值
    k = 5

    # 测试 KNN 算法
    predictions = []
    for test_row in test_data:
        prediction = predict_classification(train_data, test_row[1:], k)
        predictions.append(prediction)

    # 计算准确率
    accuracy = sum(1 for pred, label in zip(predictions, y_test) if pred == label) / len(y_test)
    print(f"Accuracy: {accuracy:.2f}")
